import java.util.*;

public class TestDemo5 {
    public static boolean judge(String str) {
        // write code here\
        if (str.length() == 0) {
            return true;
        }
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main2(String[] args) {
        String str = "abcba";
        System.out.println(judge(str));
    }


    //求平方根（二分查找法）
    public int sqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x < 4) {
            return 1;
        }
        int left = 0;
        int right = x;
        while (left <= right) {
            long mid = (left + right) / 2;
            if (mid * mid == x) {
                return (int) mid;
            } else if (mid * mid > x) {
                right = (int) mid - 1;
            } else {
                left = (int) mid + 1;
            }
        }
        //例如x为5的根号为2，2的平方小于4，right会一直减知道小于left
        return right;
    }


    //求出数组中前k个最小元素
    public static int[] topK(int[] array, int k) {
        //创建一个大根堆
        PriorityQueue<Integer> maxHead = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //遍历数组当中的元素，前k个元素放到队列当中
        for (int i = 0; i < array.length; i++) {
            if (maxHead.size() < k) {
                maxHead.offer(array[i]);
            } else {
                //从k+1个元素开始，每个元素和堆顶元素进行比较
                int top = maxHead.peek();
                if (top > array[i]) {
                    //弹出堆顶元素
                    maxHead.poll();
                    maxHead.offer(array[i]);
                }
            }
        }
        int[] tem = new int[k];
        for (int i = 0; i < k; i++) {
            tem[i] = maxHead.poll();
        }
        return tem;
    }

    public static void main1(String[] args) {
        int[] array = {5, 13, 8, 15, 6, 9};
        int[] ret = topK(array, 3);
        System.out.println(Arrays.toString(ret));
    }


    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHead = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return o2.get(0) + o2.get(1) - o1.get(0) + o1.get(1);
            }
        });
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                if (maxHead.size() < k) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxHead.offer(list);
                } else {
                    int top = maxHead.peek().get(0) + maxHead.peek().get(1);
                    if (top > nums1[i] + nums2[j]) {
                        maxHead.poll();
                        List<Integer> list = new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        maxHead.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < k && !maxHead.isEmpty(); i++) {
            list.add(maxHead.poll());
        }
        return list;
    }

    public static void main4(String[] args) {
        int[] nums1 = {1, 2};
        int[] nums2 = {1, 3};
        List<List<Integer>> ret = kSmallestPairs(nums1, nums2, 2);
        System.out.println(ret);
    }
}
    class TestHeap {
        public int[] elem;
        public int usedSize;

        public TestHeap() {
            this.elem = new int[10];
        }

        public void createHeap(int[] array) {
            for (int i = 0; i < array.length; i++) {
                elem[i] =array[i];
                usedSize++;
            }
            for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
                shifDown(parent,usedSize);
            }
        }
        //向下调整
        public void shifDown(int parent,int len){
            int child=2*parent+1;
            while(child<len){
                if(child+1<len&&elem[child]<elem[child+1]){
                    child++;
                }
                if(elem[child]>elem[parent]){
                    int tem=elem[child];
                    elem[child]=elem[parent];
                    elem[parent]=tem;
                    parent=child;
                    child=2*parent+1;
                }
                else {
                    break;
                }
            }
        }
        //向上调整(添加元素)
        public void shifUp(int child){
            int parent=(child-1)/2;
            while(child>0){
                if(elem[child]>elem[parent]){
                    int tem=elem[child];
                    elem[child]=elem[parent];
                    elem[parent]=tem;
                    child=parent;
                    parent=(child-1)/2;
                }
                else {
                    break;
                }
            }
        }
    }


